翻訳と辞書
Words near each other
・ Director of the National Security Agency
・ Director of the Office of Naval Intelligence
・ Director of the Royal Artillery
・ Director of the Royal Collection
・ Director of the Royal Greenwich Observatory
・ Director of the Royal Institution
・ Director of the United States Census Bureau
・ Director of the United States Fish and Wildlife Service
・ Director of the United States Mint
・ Director of the United States Secret Service
・ Director of the Victoria and Albert Museum
・ Director Park
・ Director primacy
・ Director Secondary Education, Haryana
・ Director Special Forces
Director string
・ Director telephone system
・ Director X
・ Director's chair
・ Director's Company
・ Director's cut
・ Director's cut (disambiguation)
・ Director's Cut (film)
・ Director's Cut (Helldorado album)
・ Director's Cut (Kate Bush album)
・ Director's Cut Awards
・ Director's Kut Productions
・ Director's law
・ Director's Report
・ Director's Special


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Director string : ウィキペディア英語版
Director string
In mathematics, in the area of lambda calculus and computation, directors or director strings are a mechanism for keeping track of the free variables in a term. Loosely speaking, they can be understood as a kind of memoization for free variables; that is, as an optimization technique for rapidly locating the free variables in a term algebra or in a lambda expression. Director strings were introduced by Kennaway and Sleep in 1982 and further developed by Sinot, Fernández and Mackie 〔F.-R. Sinot, M. Fernández and I. Mackie. Efficient Reductions with Director Strings. In ''Proc. Rewriting Techniques and Applications''. Springer LNCS vol 2706, 2003〕 as a mechanism for understanding and controlling the computational complexity cost of beta reduction.
==Motivation==
In beta reduction, one defines the value of the expression on the left to be that on the right:
:(\lambda x.E)y \equiv E(y )\, or (\lambda x.E)y \equiv E() (Replace all ''x'' in ''E''(body) by ''y'')
While this is a conceptually simple operation, the computational complexity of the step can be non-trivial: a naive algorithm would scan the expression ''E'' for all occurrences of the free variable ''x''. Such an algorithm is clearly ''O''(''n'') in the length of the expression ''E''. Thus, one is motivated to somehow track the occurrences of the free variables in the expression. One may attempt to track the position of ''every'' free variable, wherever it may occur in the expression, but this can clearly become very costly in terms of storage; furthermore, it provides a level of detail that is not really needed. Director strings suggest that the correct model is to track free variables in a hierarchical fashion, by tracking their use in component terms.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Director string」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.